
/**
 * 
 * 判断是不是平衡二叉树
 * 
 * 描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
样例解释：

样例二叉树如图，为一颗平衡二叉树
注：我们约定空树是平衡二叉树。

数据范围：
n
≤
100
n≤100,树上节点的val值满足 
0
≤
n
≤
1000
0≤n≤1000
要求：空间复杂度
O
(
1
)
O(1)，时间复杂度 
O
(
n
)
O(n)
输入描述：

输入一棵二叉树的根节点
返回值描述：

输出一个布尔类型的值
 * 
 */
public class 判断是不是平衡二叉树 {
    
    public static void main(String[] args) {
        
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        System.out.println(IsBalanced_Solution(root));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    public static boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here

        if(null == pRoot) return true;

        int leftHeigth = nodeHeight(pRoot.left);
        int rightHeigth = nodeHeight(pRoot.right);


        return Math.abs(leftHeigth - rightHeigth) <=1 
        && IsBalanced_Solution(pRoot.left)
         && IsBalanced_Solution(pRoot.right);
    }

    //计算节点高度
    private static int nodeHeight(TreeNode node){

        if(null == node) return 0;

        return Math.max(nodeHeight(node.left), nodeHeight(node.right)) + 1;

    }
}
